#include "graf.h"

#include <ctime>
#include <iostream>
#include <fstream>
#include <omp.h> 

using namespace std;

graf::graf(int w)
{
	this->wierzcholki = w;

	this->data = new bool * [w];
	for(int i=0; i<w; i++)
		data[i] = new bool[w];

	this->lista_sasiedztwa = new lista[w];

	this->stos = new lista();
	this->wynik = new lista();
}

void graf::losuj()
{
	//srand(time(0));
	int i,j;
	
	#pragma omp parallel for schedule(static, 1) default(shared) private(i, j)
	for( i=0; i<this->wierzcholki; i++)
	{
		for( j=0; j<this->wierzcholki; j++)
		{
			if(i==j) this->data[i][j] = 0;
			//else this->data[i][j] = rand() % 2;
			else
			{
				if( (rand() % 100) < 99 ) this->data[i][j] = rand() % 2;
				else this->data[i][j] = 0;
			}
		}
	}
}

void graf::losuj_graf_nieskierowany()
{
	int i, j;

    #pragma omp parallel for schedule(static, 1) default(shared) private(i, j)
	for(i=0; i<this->wierzcholki; i++)
	{
		for(j=0; j<this->wierzcholki; j++)
		{
			if(i==j) this->data[i][j] = 0;
			//else this->data[i][j] = rand() % 2;
			else
			{
				bool tmp = rand() % 2;

				if( (rand() % 100) < 90 )
				{
					this->data[i][j] = tmp;
					this->data[j][i] = tmp;
				}	
				else
				{
					this->data[i][j] = 0;
					this->data[j][i] = 0;
				}
			}
		}
	}
}

int graf::stopien_wierzcholka(int w)
{
	int deg = 0,i;
	#pragma omp parallel  default(shared)  private(i) reduction(+ : deg) 
	{
	for( i=0; i<this->wierzcholki; i++)
	{
		//wierzcholki wychodzace
		if(this->data[w][i] == 1) deg++;
		
		//wierzcholki wchodzace
		if(this->data[i][w] == 1) deg--;
	}
	}

	return deg;
}

bool graf::parzysty(int w)
{
	int deg = 0, i=0;
	//#pragma omp parallel  default(none) shared(w) private(i) reduction(+ : deg) 
	for( i=0; i<this->wierzcholki; i++)
	{
		if(this->data[w][i] == 1) deg++;
	}
	

	if(deg % 2 == 0) return true;
	else return false;
}

bool graf::czy_posiada_droge(int start, int finish)
{
	if(this->data[start][finish] == 1) return true;
	else return false;
}

void graf::sprawdz_warunki()
{
	int i, j;

    #pragma omp parallel for schedule(static, 1) default(shared) private(i, j)
	for (i=0; i<this->wierzcholki-1; i++) 
	{
		    //licz stopien
			int deg = this->stopien_wierzcholka(i);
			
			if(deg > 0)
			{
				for(j=i+1; j<this->wierzcholki; j++)
				{
					//usuniecie drogi wychodzacej
					if(this->czy_posiada_droge(i, j))
					{
						this->data[i][j] = 0;
						deg--;
						if(this->stopien_wierzcholka(i) == 0) break;
					}

					//dodanie drogi wchodzacej
					if(!this->czy_posiada_droge(j, i))
					{
						this->data[j][i] = 1;
						deg--;
						if(this->stopien_wierzcholka(i) == 0) break;
					}
				}
			}
			else if(deg < 0)
			{
				for(int j=i+1; j<this->wierzcholki; j++)
				{
					//dodanie drogi wychodzacej
					if(!this->czy_posiada_droge(i, j))
					{
						this->data[i][j] = 1;
						deg++;
						if(this->stopien_wierzcholka(i) == 0) break;
					}

					//uduniecie drogi wchodzacej
					if(this->czy_posiada_droge(j, i))
					{
						this->data[j][i] = 0;
						deg++;
						if(this->stopien_wierzcholka(i) == 0) break;
					}
				}
			}
	}
}

void graf::sprawdz_warunki_graf_nieskierowany()
{
	int i, j;

    #pragma omp parallel for schedule(static, 1) default(shared) private(i)
	for(i=0; i<this->wierzcholki-1; i++)
	{
		if(!this->parzysty(i))
		{
			if(this->czy_posiada_droge(i, i+1))
			{
				this->data[i][i+1] = 0;
				this->data[i+1][i] = 0;
			}
			else
			{
				this->data[i][i+1] = 1;
				this->data[i+1][i] = 1;
			}
		}
	}
}

void graf::tworz_liste_sasiedztwa()
{
	int i, j;

	//#pragma omp parallel for schedule(static, 1) default(shared) private(i, j)
	for(i=0; i<this->wierzcholki; i++)
	{
		for(j=0; j<this->wierzcholki; j++)
		{
			if(this->data[i][j] == 1)
				this->lista_sasiedztwa[i].add(j);
		}
	}
}

void graf::szukaj_sciezki(int start)
{
	this->stos = new lista();
	this->wynik = new lista();

	while(this->lista_sasiedztwa[start].isEmpty()) start++;

	if(start >= this->wierzcholki) return;

	this->stos->add(this->lista_sasiedztwa[start].get());
	this->lista_sasiedztwa[start].del();

	/*cout << "Dane startowe: " << endl;
	cout << "stos: "; this->stos->wypisz();
	cout << endl << "lista sasiedztwa: " << endl; this->wypisz_liste_sasiadztwa();
	cout << endl;
	system("PAUSE");*/

	while(!this->stos->isEmpty())
	{

		if(this->lista_sasiedztwa[this->stos->get()].isEmpty())
		{
			//cout << "sciezka: " << this->stos->get() << ", ";
			this->wynik->add(this->stos->get());
			this->stos->del();
		}
		else
		{	int tmp = this->stos->get();

			this->stos->add(this->lista_sasiedztwa[tmp].get());
			//this->lista_sasiedztwa[this->stos->get()].del();
			this->lista_sasiedztwa[tmp].del();
		}

		/*cout << endl << "stos: ";
		this->stos->wypisz();
		cout << endl << "l sasiedztwa: " << endl;
		this->wypisz_liste_sasiadztwa();
		cout << endl;
		system("pause");*/

		/*cout << "stos: "; this->stos->wypisz();
		cout << endl << "lista sasiedztwa: " << endl; this->wypisz_liste_sasiadztwa();
		cout << endl;
		system("PAUSE");*/

	}
}

void graf::szukaj_sciezki_rekurencyjnie(int w)
{
	this->stos = new lista();
	this->wynik = new lista();

	while(!this->lista_sasiedztwa[w].isEmpty())
	{
		// zapamietaj ostatni element listy
		int x = this->lista_sasiedztwa[w].get();

		// usun ostatni element listy
		this->lista_sasiedztwa[w].del();

		this->szukaj_sciezki_rekurencyjnie(x);
	}

	// zapamietaj pusty wierzcholek
	this->wynik->add(w);
}

void graf::szukaj_sciezki_nieskierowanej_rekurencyjnie(int w, int emo)
{
	while(!this->lista_sasiedztwa[w].isEmpty())
	{
		// zapamietaj ostatni element listy
		int x = this->lista_sasiedztwa[w].get();

		// usun ostatni element listy
		this->lista_sasiedztwa[w].del();

		int i;

		element * znaleziony;
		element * tmp;

		//#pragma omp parallel for schedule(static, 1) default(shared) private(i, tmp)
		for( i=0; i<this->lista_sasiedztwa[x].getCount(); i++)
		{	
			tmp = this->lista_sasiedztwa[x].getElementIfEqual(i, w);

			if(tmp != NULL)
			{
				znaleziony = tmp;
				//this->lista_sasiedztwa[x].delPointer(tmp);
			}	
		}
		
		this->lista_sasiedztwa[x].delPointer(znaleziony);

		this->szukaj_sciezki_nieskierowanej_rekurencyjnie(x, w);
	}

	// zapamietaj pusty wierzcholek
	this->wynik->add(w);
}

void graf::wypisz_tablice()
{
	for(int i=0; i<this->wierzcholki; i++)
	{
		for(int j=0; j<this->wierzcholki; j++)
		{
			cout << this->data[i][j] << ", ";
		}
	cout << endl;
	}
}

void graf::wypisz_liste_sasiadztwa()
{
	for(int i=0; i<this->wierzcholki; i++)
	{
		cout << "wierzcholek " << i << ": ";
		this->lista_sasiedztwa[i].wypisz();
		cout << endl;
	}
}

void graf::wypisz_stopnie_wierzcholkow()
{
	for(int i=0; i<this->wierzcholki; i++)
	{
		cout << "stopien wierzcholka " << i << ": " << this->stopien_wierzcholka(i) << endl;
	}
}

void graf::wypisz_wynik()
{
	this->wynik->wypisz();
}

void graf::wypisz_parzystosc()
{
	for(int i=0; i<this->wierzcholki; i++)
	{
		cout << "wierzcholek " << i << " parzysty? : " << this->parzysty(i) << endl;
	}
}

int graf::wczytaj_rozmiar()
{int tmp1;
	ifstream wedane("doodczytu.txt", ios::in);
	//spr odczytu
	if(!wedane){
	cerr<<"plik nie moze byc odczytany"<<endl;
	exit(1);
	}
	wedane>>tmp1;
return tmp1;
}

void graf::wczytaj_tablice()
{
int tmp1, tmp2;
	ifstream wedane("doodczytu.txt", ios::in);
	//spr odczytu
	if(!wedane){
	cerr<<"plik nie moze byc odczytany"<<endl;
	exit(1);
	}
	int i,j;
	//#pragma omp parallel default(none) private(i, j,tmp2) shared(tmp1) 
	//{
		#pragma omp single
		{ 
		wedane>>tmp1;
		}
	
	//#pragma omp for schedule(dynamic) 
//	{
		for( i=0; i<tmp1; i++)
		{
			for( j=0; j<tmp1; j++)
			{	wedane>>tmp2;
				if(tmp2 == 1)
				this->lista_sasiedztwa[i].add(j);
			}
		}
	//}
	//}
}

void graf::zapisz_tablice()
{
	ofstream wy_dane("dozapisu.txt", ios::out);
	//spr odczytu
	if(!wy_dane){
	cerr<<"plik nie moze byc zapisany"<<endl;
	exit(1);
	}
	wy_dane<<this->wierzcholki;
	for(int i=0; i<this->wierzcholki; i++)
	{wy_dane<<endl;
		for(int j=0; j<this->wierzcholki; j++)
		{
			wy_dane<<data[i][j]<<" ";
				
		}
	}
	wy_dane.close();
	cout<<"powodzenie zapisu"<<endl;
}
void graf::wyn_wielowatkowy(int ile)
{for(int i=0;i<ile-1;i++)wynik->del();

}